import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-02-14
 * Time:13:11
 */

/**
 * 540. 有序数组中的单一元素
 * 给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
 * <p>
 * 请你找出并返回只出现一次的那个数。
 * <p>
 * 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class TestDemo {
    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 3, 3, 4, 4, 8, 8};
        System.out.println(singleNonDuplicate3(nums));
    }

    public static int singleNonDuplicate(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int a : nums) {
            if (list.contains(a)) {
                list.remove((Object) a);
            } else {
                list.add(a);
            }
        }
        return list.get(0);
    }

    //最简单的方法是以「步长为 22」的方式进行从前往后的遍历，找到第一个不符合「与后一个数相等」条件的值即是答案。
    public static int singleNonDuplicate1(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i += 2) {
            if (nums[i] != nums[i + 1]) { //成对遍历
                return nums[i];
            }
        }
        //如果前面都成对 则最后一个是答案
        return nums[n - 1];
    }

    //利用异或 0^任何数=任何数
    //a^a = 0;

    /***异或1的结果有两种：
     如果本身是奇数，那么异或1之后得到的结果必然为偶数；
     如果本身是偶数，那么异或1之后得到的结果必然为奇数
     两个数异或的结果去异或其中一个数，其结果一定是另一个数*/
    public static int singleNonDuplicate2(int[] nums) {
        int ans = 0;
        for (int a : nums) {
            ans = ans ^ a;
        }
        return ans;
    }

    //
    public static int singleNonDuplicate3(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (mid % 2 == 0) {
                if (mid + 1 < n && nums[mid] == nums[mid + 1]) l = mid + 1;
                else r = mid;
            } else {
                if (mid - 1 >= 0 && nums[mid - 1] == nums[mid]) l = mid + 1;
                else r = mid;
            }
        }
        return nums[r];
    }
}
